An emerging development in computer organization is the use of data compression for the contents of main memory, that part of the random access memory hierarchy which is managed by the operating system (“OS”) and where the unit of allocation is a page.
In compressed memory systems, a page may occupy a variable amount of physical memory space. For example, as described in the aforementioned related patent applications, pages occupy or share a variable number of fixed size blocks; pages may be of nominal 4K size and blocks of size 256 bytes. Generally, the number of such blocks occupied by a page will vary with its contents, due to changes in compressibility.
Typically, each cache line is compressed prior to being written into memory, using a standard sequential or a parallel compression algorithm. Examples of sequential compression include Lempel-Ziv coding (and its sequential and parallel variations), Huffman coding and arithmetic coding. See, for example, J. Ziv and A. Lempel, “A Universal Algorithm For Sequential Data Compression,” IEEE Transactions on Information Theory, IT-23, pp. 337–343 (1977) which is hereby incorporated by reference in its entirety. A parallel approach is described in co-pending U.S. patent application Ser. No. 08/498,948, entitled Parallel Compression and Decompression Using a Cooperative Dictionary, by Franaszek et al., filed on Jul. 6, 1995 (“Franaszek”). The Franaszek patent application is commonly assigned with the present invention to IBM Corporation, Armonk, N.Y. and is hereby incorporated herein by reference in its entirety. A convenient way to perform this compression is by automatically compressing the data using special-purpose hardware, with a minimum of intervention by the software or operating system. This permits compression/decompression to be done rapidly, avoiding what might otherwise be long delays associated with software compression/decompression.
Changes to a page stored in main memory occur on write backs from the cache. That is, a changed cache line may require a larger number of blocks on write back, than previously. If there are an insufficient number of free blocks to hold the changed line, the system abends. Thus, there is a need to maintain adequate free space under fluctuating compression efficiencies. There is also a need as in current operating systems, to maintain adequate free space for new pages, or pages to be brought into main memory from disk storage. The present invention addresses these needs.
A difference between a system of this kind, and a traditional system (without compression) is that in the traditional system, allocation (also called commitment) of a page to a program is the same as allocating a “page frame,” that is, real storage, as opposed to some unknown number of blocks (after compression). Moreover, after allocation, the contents of a new page must be written back to storage from the cache, so that there is a variable delay between storage allocation and storage utilization. During this variable delay, the corresponding storage will be referred to as being “allocated but unused.” Also, in general, there is no indication to the application or system software when a given line is cast out from the cache. Thus, there is uncertainty related to the amount of storage that has been committed to new pages, but which is not yet reflected in storage utilization. A consequence is the possible over commitment of storage and the accompanying performance degradation and/or system abends. The present invention addresses these problems.